package day11;

//题目链接：https://www.nowcoder.com/questionTerminal/572903b1edbd4a33b2716f7649b4ffd4
public class 买股票的最佳时机2 {
	//最优解：贪心
	public static void main1(String[] args) {
		Scanner in = new Scanner(System.in);
		// 注意 hasNext 和 hasNextLine 的区别
		while (in.hasNextInt()) { // 注意 while 处理多个 case
			int n = in.nextInt();
			int[] prices=new int[n];
			for(int i=0;i<n;i++){
				prices[i]=in.nextInt();
			}
			//由于最多只能进行一次买入/卖出，且可以进行无限次的买入，卖出操作，
			//因此，只要有收益就应该买入并卖出
			//=>任意相邻的两个如果有收益，就进行买入与卖出，遍历所有天后就收益最大了；
			int ret=0;
	        for(int i=1;i<prices.length;i++){
	            if(prices[i]-prices[i-1]>0){
	                ret+=prices[i]-prices[i-1];
	            }
	        }
			System.out.println(ret);
		}
	}
	
	
	
	//次优解：动态规划
	public static void main1(String[] args) {
		Scanner in = new Scanner(System.in);
		// 注意 hasNext 和 hasNextLine 的区别
		while (in.hasNextInt()) { // 注意 while 处理多个 case
			int n = in.nextInt();
			int[] prices=new int[n];
			for(int i=0;i<n;i++){
				prices[i]=in.nextInt();
			}
			//1.状态表示:
			// f[i]:第i天处于买入状态，能获得的最大收益
			// g[i]:第i天处于卖出状态，能获得的最大收益
			//2.状态转移方程：
			// f[i]=max(g[i-1]-prices[i],f[i-1])
			// g[i]=max(g[i-1],f[i-1]+prices[i])
			int[] f=new int[n];
			int[] g=new int[n];
			f[0]=-prices[0];
			g[0]=0;
			for(int i=1;i<n;i++){
				f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
				g[i]=Math.max(g[i-1],f[i-1]+prices[i]);
			}
			System.out.println(g[n-1]);
		}
	}
}
